Introduction to Machine Learning

Unit 06: ROC Curve, AUC, and the Curse of Dimensionality

1. Introduction

Classifiers produce scores (posterior probabilities, distance-weighted votes) before applying a threshold. The ROC curve visualizes every possible threshold tradeoff and lets us (a) compare models via AUC, and (b) pick an optimal probability threshold for deployment. This unit also revisits the curse of dimensionality with concrete geometry that motivates the feature selection & extraction methods of the next two units.

Learning Objectives

2. Theory

2.1 From Class Labels to Probabilities

Most classifiers can return a continuous score, not just a binary label. For KNN with K=19, if 13 neighbors say + and 6 say −, then:

\( P(+ \mid \mathbf{x}) = \frac{13}{19} \approx 0.68 \)

Default threshold: classify as + if P ≥ 0.5. But 0.5 is arbitrary! We should pick thresholds based on the cost of each error type, not default conventions.

2.2 Thresholds Trade Off TPR vs. FPR

How threshold changes affect TPR and FPR A vertical diagram showing that moving the classification threshold from zero to one decreases both true positive rate and false positive rate, with intermediate thresholds between them. Threshold moves from 0 → 1 A stricter threshold changes what the classifier calls “positive” 0.1 LOW THRESHOLD Predict + freely A small score is enough to trigger a positive prediction. High TPR catch most real +’s High FPR lots of false alarms increase threshold INTERMEDIATE THRESHOLDS ⋯ 0.2 · 0.5 · 0.7 ⋯ increase threshold 0.9 HIGH THRESHOLD Predict + only when extremely confident Only the strongest scores are treated as positive. Low TPR miss many real +’s Low FPR very few false alarms KEY INSIGHT You cannot increase TPR without also increasing FPR — unless the classifier improves.

2.3 Constructing the ROC Curve

Step-by-step algorithm

  1. For every test instance, obtain the classifier's score s = P(+|X).
  2. Sort all instances in descending order of s (most confident + on top).
  3. Place a candidate threshold between every unique score value.
  4. At each candidate threshold, count TP, FP, TN, FN. Compute:
\( TPR = \text{Sensitivity (Recall)} = \frac{TP}{TP + FN} \qquad\text{(y-axis)} \)

\( FPR = 1 - \text{Specificity} = \frac{FP}{FP + TN} \qquad\text{(x-axis)} \)

Plot each (FPR, TPR) pair. Connect the dots. The result is the ROC curve. It always passes through (0,0) (threshold=1, predict nobody) and (1,1) (threshold=0, predict everybody). Best classifier = hugs the upper-left corner (0,1).

2.4 AUC — Area Under the ROC Curve

2.5 Comparing Models with ROC

Northwest dominance rule

Given two candidate thresholds (or two different models) plotted as points on the FPR-TPR plane:

Point A dominates point B iff A is strictly to the northwest of B: lower FPR AND higher TPR.

If neither dominates the other — one has higher TPR but also higher FPR — which is "better" depends on the per-error costs that the deployment environment assigns.

Example from lecture: Point (0.1, 0.6) dominates (0.2, 0.5) → lower FPR + higher TPR. But (0.1, 0.6) vs. (0.2, 0.7)? The latter has higher TPR but worse FPR, so deployment cost structure decides.

2.6 Choosing the Optimal Operating Threshold

Two automated methods to pick the single "best" point along the ROC curve.

Euclidean Distance Method
Youden's J Statistic

Distance from the perfect classifier at (FPR = 0, TPR = 1):

\( \text{Euc} = \sqrt{(1 - TPR)^2 + FPR^2} \)

Minimize Euc across all candidate ROC points. Smallest = 0 for a perfect classifier; largest = √2 ≈ 1.414 for a (1, 0) useless classifier. Measures "how close to ideal corner?"

Maximize vertical distance above the diagonal line. Very popular in medical literature.

\( J = TPR - FPR \quad\text{or equivalently}\quad Sensitivity + Specificity - 1 \)

Range [0, 1]. J = 1 only when perfect (TPR=1, FPR=0). J = 0 when the point sits on the random diagonal.

2.7 ROC Curve — What It's Used For (2 Main Jobs)

  1. Model comparison via AUC (area): Pick the classifier/model with the larger AUC. Good overall measure of ranking quality, threshold-agnostic.
  2. Threshold optimization: After choosing the model, find the point on that model's ROC curve that optimizes your deployment cost function (Euc, Youden, or custom cost-weighted FPR/TPR tradeoff) → set that threshold in production.

2.8 Curse of Dimensionality

Adding more features is not free. In fact, it breaks distance-based methods geometrically.

Why algorithms react differently to noise features

Given additional features that are pure noise (no relation to target):

2.9 The Hypercube Thought Experiment

Concrete example from lecture. All features uniformly distributed over [0, 1]. We want to classify a query at X = 0.6 using the 10% nearest neighbors rule (use only training samples whose features all fall within ±5% of the feature range, i.e., 10% of the axis length):

\( \text{Fraction of hypercube captured by a 10\% local neighborhood in } p \text{ dimensions} = (0.1)^p \)
p (dimensions)Fraction of data coveredData you need for 10 observations in neighborhood
p = 110% (0.1)100 rows
p = 21% (0.01)1,000 rows
p = 30.1% (0.001)10,000 rows
p = 100.0000001%10 billion rows

Takeaway: In high dimensions, the local 10% neighborhood is essentially the entire dataset. There is no concept of "nearby." The distance between any two randomly chosen points becomes approximately the same constant. KNN's core assumption — that nearby points share a label — fails catastrophically.

In high dimensions, everyone is your neighbor... and no one is.

3. Interactive Examples

Example 1: Construct ROC by Hand

Ten test instances with their true class and a classifier's P(+|A):

Instance12345678910
P(+|A)0.950.930.870.850.800.780.760.530.430.25
True Class++−+−+−−−+
Step 1: Compute accuracy at threshold 0.5 (click)

Predict + for rows 1–8 (P ≥ 0.5), − for 9, 10. Truths of those: {+,+,−,+,−,+,−,−} → 5 + and 3 − predictions.

TP = # of predicted + that are real + = rows 1,2,4,6 = 4.

FP = # of predicted + that are real − = rows 3,5,7,8 = 4.

TN = # predicted − that are real − = row 9 = 1.

FN = # predicted − that are real + = row 10 = 1.

Accuracy = (4+1)/10 = 50%. Pretty bad at threshold 0.5!

Step 2: Compute accuracy at thresholds 0.87 and 0.43

Threshold 0.87: Predict + for rows 1,2,3. Truths: +,+,−. TP=2, FP=1, TN=4 (all negatives 5,7,8,9), FN=3 (miss + at rows 4,6,10). Acc = (2+4)/10 = 60%.

Threshold 0.43: Predict + for 1–9, − for 10. Truths: +,+,−,+,−,+,−,−,−. TP=4, FP=5 (rows 3,5,7,8,9), TN=0, FN=1 (row 10). Acc = (4+0)/10 = 40%.

Threshold 0.87 is better than 0.5, which in turn beats 0.43. ROC lets you find the global best, not just test three arbitrary cuts.

Example 2: Northwest Point Comparison

Six candidate threshold points (FPR, TPR) = (0.1,0.6), (0.2,0.5), (0.4,0.2), (0.5,0.5), (0.7,0.7), (0.2,0.7).

  1. Which one dominates (0.2, 0.5)? (northwest rule)
  2. Which pair(s) are incomparable (neither strictly dominates the other)?
  3. Compute Euc for (0.2, 0.7) and for (0.1, 0.6). Which minimizes Euc?

(a) (0.1, 0.6) FPR↓ and TPR↑ both better. It strictly dominates.

(b) E.g., (0.1, 0.6) vs. (0.2, 0.7): the second has higher TPR but worse FPR. Neither dominates → incomparable.

(c)

Euc(0.2, 0.7) = √(0.3² + 0.2²) = √0.13 ≈ 0.3606 Euc(0.1, 0.6) = √(0.4² + 0.1²) = √0.17 ≈ 0.4123

(0.2, 0.7) is closer to (0, 1) by Euclidean distance → it wins under Euc despite having higher FPR, because its TPR of 0.7 is much closer to 1 than 0.6.

Example 3: Curse — Hypercube Neighborhood Size

Neighborhood Coverage Calculator 📐

Uniform data on [0,1]^p. You want to capture a 5% neighborhood along each axis so you look at points that fall in [x − 0.025, x + 0.025] on every axis.

  1. What fraction of the space is covered in p = 2, 5, and 20 dimensions?
  2. Suppose you want on average 50 observations inside the neighborhood. How many total rows do you need in your dataset at p = 2, 5, 20?

(a) Coverage fraction = (0.05)^p.

p=2: (0.05)² = 0.25% p=5: (0.05)^5 = 3.125 × 10⁻⁷ ≈ 0.00003% p=20: (0.05)^20 ≈ 9.5 × 10⁻²⁷ (essentially zero!)

(b) Required dataset size N = 50 / coverage:

p=2: N = 50 / 0.0025 = 20,000 rows p=5: N ≈ 50 / 3.125e-7 = 160,000,000 rows p=20: ~ 5.3 × 10²⁷ rows → more than the age of the universe in seconds. Impossible.

This is exactly why feature reduction (selection + extraction: Units 7–8) is mandatory before KNN on wide data.

4. Numerical Solutions

Problem 1: Full ROC Table Construction

Build the full ROC table for the 10 instances from Example 1. Each unique P(+|A) score becomes a threshold.

📘 Full solution table (click)
Threshold ≥Predict +: rowsTPFPTNFNTPRFPREucJ (Youden)
1.00 (nobody)∅00550.00.01.0000.0
0.95{1}10540.20.00.8000.2
0.93{1,2}20530.40.00.6000.4
0.87{1,2,3}21430.40.20.6320.2
0.851–431420.60.20.4470.4
0.801–532320.60.40.5660.2
0.781–642310.80.40.4470.4
0.761–743210.80.60.6320.2
0.531–844110.80.80.8250.0
0.431–945010.81.01.020−0.2
0.25 (all)1–1055001.01.01.0000.0

Minimum Euc = 0.447 occurs at two tied points: (0.85 threshold, FPR=0.2, TPR=0.6) and (0.78 threshold, FPR=0.4, TPR=0.8). A tie! The first has higher Precision (low FPR), the second has higher Recall (high TPR) — deployment cost structure picks between them.

Maximum Youden J = 0.4 is achieved by (0.93 threshold, 0.4/0), (0.85 threshold, 0.6/0.2), and (0.78 threshold, 0.8/0.4). A 3-way tie that reflects the small n=10 test set.

Problem 2: Youden Index vs. Euclidean Distance

Two candidate threshold points on ROC: Point M = (FPR 0.15, TPR 0.75), Point N = (FPR 0.25, TPR 0.90).

  1. Compute Euc for M and N. Which minimizes it?
  2. Compute Youden J for M and N. Which maximizes it?
  3. Interpret: why do the two criteria disagree on which is "best"? When would each be preferred?
📘 Step-by-step solution

(a)

Euc(M) = √((1-0.75)² + (0.15)²) = √(0.0625 + 0.0225) = √0.085 ≈ 0.2915 Euc(N) = √(0.10² + 0.25²) = √(0.01 + 0.0625) = √0.0725 ≈ 0.2693 ✅ smaller

Euc prefers N.

(b)

J(M) = 0.75 − 0.15 = 0.60 ✅ larger J(N) = 0.90 − 0.25 = 0.65 → actually bigger (J wins N too here!)

Both prefer N. If we construct a counterexample point Q = (0.01, 0.6) then Euc = 0.400, J = 0.59 — Euc would prefer N over Q but J would prefer Q over N, because Euc punishes TPR distance from 1 heavily (squared) while J treats TPR and FPR linearly equal.

(c) Euc weights "distance from the corner" in squared Euclidean space → small movements near the TPR=1 axis count more. Youden treats TPR and FPR linearly equal. If missing a positive (low TPR) and a false alarm (high FPR) cost literally the same dollar amount, use J. If getting near-perfect TPR is disproportionately important (medical), Euc (or the equivalent β-heavy F_metric) is more natural.

Problem 3: KNN and Dimensionality

You run KNN on 3 different feature subsets of a 500-row dataset, getting 10-fold CV accuracy of 89% using p=4 features; 85% using p=40 features; and 72% using p=400 features. The true information content is actually contained in those 4 features.

  1. Name and explain the phenomenon causing accuracy to drop as p grows despite the same underlying ground truth.
  2. Why does accuracy drop steadily rather than stay the same?
  3. What three actions would recover most of the lost performance?
📘 Step-by-step solution

(a) Curse of Dimensionality on KNN. As feature count grows, the extra 36 (and then 396) noise dimensions inflate distances between every pair of points, swamping the useful signal in the first 4 dimensions. KNN cannot tell "true nearby" from "randomly close on noise axes."

(b) Distances become less discriminative uniformly — the ratio of (nearest neighbor distance / farthest neighbor distance) → 1 in high dimensions. More and more of the K nearest neighbors are actually of the wrong class because label structure doesn't correlate with the noise dimensions at all.

(c) Recovery menu: (i) Filter feature selection / ANOVA / MI to prune dimensions. (ii) Wrapper selection (forward/backward — Unit 08). (iii) PCA extraction (Unit 08) onto a low-dim subspace before KNN. (iv) Switch classifier to Random Forest which ignores noise features (doesn't fix KNN but sidesteps the curse for the modeling step).

5. Try It Yourself

Problem 1 — AUC Rank Interpretation

A model reports AUC = 0.85 on a binary classification test set with 500 positives and 500 negatives. Suppose I take a uniformly random positive and a uniformly random negative and compare their P(+|X) scores. What's the probability the positive's score is strictly greater? If I compare 100 independent positive-negative pairs, how many do I expect to be correctly ordered?

Probability of correct ordering = AUC = 85% (that is exactly the probabilistic interpretation of AUC!). Expected number out of 100 independent pairs = 100 × 0.85 = 85 correctly ordered.

Problem 2 — Optimal Threshold Selection

Four ROC operating points with (FPR, TPR) = (0.02, 0.60), (0.05, 0.80), (0.20, 0.96), (0.50, 0.99). Find: (a) Euclidean-minimizing, (b) Youden J-maximizing, (c) the choice for a costly-miss disease screening where TPR is 5× more important than FPR, and (d) the choice for a spam filter where FP (good→spam) costs 10× a FN (spam in inbox).

Eucs: (0.02, 0.60) → √(0.4²+0.02²)=0.4005; (0.05, 0.80) → √(0.2²+0.05²)=0.206; (0.20, 0.96) → √(0.04²+0.20²)≈0.204; (0.50, 0.99) → √(0.01+0.25)=0.51. (a) Min Euc ≈ (0.20, 0.96) (by a hair over 0.80/0.05).

Js: 0.58, 0.75, 0.76, 0.49. (b) Max J = (0.20, 0.96).

(c) Disease screening: TPR dominates. Choose (0.20, 0.96) → 96% of cases caught, accepting 20% false alarm rate (which is manageable, it just means more tests). If you can go even higher TPR at any cost, pick (0.50, 0.99).

(d) Spam filter: FPR cost dominates. Pick the lowest achievable FPR point that still catches meaningful spam: (0.02, 0.60). Only 2% of ham goes to spam folder. You miss 40% of spam (that's the tradeoff) — add a second layer or accept it.

Problem 3 — Local Neighborhood Growth

p = 100 features, each uniform on [0,1]. To make a prediction at a query, KNN(k=100) on a dataset of n = 100,000 rows considers 100 nearest neighbors among 100,000. For each feature independently, what's the average local "fraction" of the feature axis that those 100 neighbors span? (Approximate: treat each axis independently, assume 100 neighbors span ~ 100/100,000 = 0.1% of the order statistics on a single axis.)

Order-statistics approximation: on any 1-D axis, the 100 nearest neighbors span roughly a fraction 100/100,000 = 0.1% of the axis length on average. So the neighborhood per feature is 0.1% of the axis. Hypercube volume fraction = (0.001)^100 = 10⁻³⁰⁰. That's far more extreme than the number of atoms in the observable universe (~10⁸⁰). In other words, even with 100k rows, in 100 dimensions the 100 "nearest" neighbors are NOT local in any meaningful sense — they are scattered across essentially the entire range of every feature. KNN's local-structure assumption collapses.

6. Interactive Quiz

Answer all 5 MCQs. Click on an option to get instant feedback.

Your score: 0 / 5

7. Key Takeaways

  1. ROC = TPR vs. FPR across all thresholds. Every point on the curve is a different operating tradeoff. Curve passes through (0, 0) and (1, 1).
  2. AUC = 0.5 → random; 1.0 → perfect ranking. AUC is also exactly P(score(+ random) > score(− random)). AUC near 0 → flip predictions to get perfect model.
  3. Northwest dominance: a point strictly northwest of another is unconditionally better. When two points are incomparable (one TPR↑ + one FPR↓), deployment costs decide.
  4. Two threshold-optimization criteria: Euc = min√((1−TPR)²+FPR²); Youden J = max(TPR−FPR). Euc weights TPR/FPR by square distance from ideal; Youden weights them linearly equal.
  5. Curse of dimensionality: In p dimensions, a local "10% neighborhood" captures only (0.1)^p of the space. For large p, this is astronomically small → KNN needs astronomically large n to find true neighbors.
  6. KNN + wide data = suffering. Distance-based methods degrade fastest; trees and Naive Bayes degrade slowest. Fix the curse before KNN: reduce dimensions via selection or extraction!

8. Common Pitfalls

  1. Always using 0.5 threshold. 0.5 is a convention, not an optimum. Compute ROC, then pick the threshold that matches your FP/FN cost ratio. Skipping this step leaves real money (or lives) on the table.
  2. Reporting only accuracy/AUC without a production threshold. AUC ranks overall quality but tells you nothing about the deployed behavior. The deployable artifact is a specific threshold on a specific score.
  3. "ROC says AUC 0.99 so accuracy must be 99% too." Nope. AUC is ranking quality across many thresholds; accuracy at a single chosen threshold can be terrible (e.g., by picking a threshold that achieves 99% TPR at 98% FPR).
  4. Running KNN on p=500 without dimension reduction. Classic high-dim failure mode. You'll get ~random performance and spend weeks debugging the algorithm instead of applying feature selection/PCA first.
  5. More features always help. False. Adding pure-noise features actively damages KNN. It doesn't stay neutral — it actively poisons the distance metric.
  6. Confusing axes on ROC. Y = TPR (Recall/Sensitivity), X = FPR (1 − Specificity). If you swap axes or label TNR instead, you miscompute everything.

9. Resources